﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithms
{
    /// <summary>
    /// 最长的不重复子串的长度
    /// https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
    /// </summary>
    public class LongestSubstringWithoutRepeatingCharacters
    {
        public static int Action1(string s)
        {
            if (string.IsNullOrEmpty(s)) { return 0; }
         
            int length=1;
            int result = 1;
            var chars= s.ToCharArray();

            List<char> sub = new List<char>();//定义子串
            foreach(var item in chars)
            {
                int index = sub.IndexOf(item);
                if (index< 0)
                {
                    sub.Add(item);
                    length = sub.Count();
                }else
                {
                    sub.RemoveRange(0,index+1);
                    sub.Add(item);
                    length = sub.Count();
                }
                if (length > result)
                {
                    result = length;
                }
               
            }
            return result;
        }
        public static int Action2(string s)
        {
            int curlen = 0;
            int result = 0;
            int last_star = 0;//上一个最长子串起始位置
            if (string.IsNullOrEmpty(s))
            {
                return result;
            }
            result = 1;

            System.Collections.Hashtable hash = new System.Collections.Hashtable();

            for(int i = 0; i < s.Length; i++)
            {
                if (hash[s[i]] == null)
                {
                    curlen=curlen+1;
                    hash[s[i]] = i;/* 记录字符下标 */
                }
                else
                {
                    if (last_star <= (int)hash[s[i]]) //如果找到的值在当前子串头之后, 将子串头置为当前值
                    {
                        curlen = i - (int)hash[s[i]];
                        last_star = (int)hash[s[i]] + 1;
                        hash[s[i]] = i; /* 更新最近重复位置 */
                    }
                    else
                    {
                        curlen = curlen + 1;
                        hash[s[i]] = i; /* 更新最近重复位置 */
                    }
                }
                if (curlen > result)
                {
                    result = curlen;
                }
            }
            return result;
        }

    }
}
